{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Adjacent Elements With the Same Color"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: colorTheArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有相同颜色的相邻元素数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始、长度为 <code>n</code>&nbsp;的数组&nbsp;<code>nums</code>&nbsp;。一开始，所有元素都是 <strong>未染色</strong>&nbsp;（值为 <code>0</code>&nbsp;）的。</p>\n",
    "\n",
    "<p>给你一个二维整数数组&nbsp;<code>queries</code>&nbsp;，其中&nbsp;<code>queries[i] = [index<sub>i</sub>, color<sub>i</sub>]</code>&nbsp;。</p>\n",
    "\n",
    "<p>对于每个操作，你需要将数组 <code>nums</code>&nbsp;中下标为&nbsp;<code>index<sub>i</sub></code>&nbsp;的格子染色为&nbsp;<code>color<sub>i</sub></code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回一个长度与 <code>queries</code>&nbsp;相等的数组<em>&nbsp;</em><code>answer</code><em>&nbsp;</em>，其中<em>&nbsp;</em><code>answer[i]</code>是前 <code>i</code>&nbsp;个操作&nbsp;<strong>之后</strong>&nbsp;，相邻元素颜色相同的数目。</p>\n",
    "\n",
    "<p>更正式的，<code>answer[i]</code>&nbsp;是执行完前 <code>i</code>&nbsp;个操作后，<code>0 &lt;= j &lt; n - 1</code>&nbsp;的下标 <code>j</code>&nbsp;中，满足&nbsp;<code>nums[j] == nums[j + 1]</code> 且&nbsp;<code>nums[j] != 0</code>&nbsp;的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]\n",
    "<b>输出：</b>[0,1,1,0,2]\n",
    "<b>解释：</b>一开始数组 nums = [0,0,0,0] ，0 表示数组中还没染色的元素。\n",
    "- 第 1 个操作后，nums = [2,0,0,0] 。相邻元素颜色相同的数目为 0 。\n",
    "- 第 2 个操作后，nums = [2,2,0,0] 。相邻元素颜色相同的数目为 1 。\n",
    "- 第 3 个操作后，nums = [2,2,0,1] 。相邻元素颜色相同的数目为 1 。\n",
    "- 第 4 个操作后，nums = [2,1,0,1] 。相邻元素颜色相同的数目为 0 。\n",
    "- 第 5 个操作后，nums = [2,1,1,1] 。相邻元素颜色相同的数目为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 1, queries = [[0,100000]]\n",
    "<b>输出：</b>[0]\n",
    "<b>解释：</b>一开始数组 nums = [0] ，0 表示数组中还没染色的元素。\n",
    "- 第 1 个操作后，nums = [100000] 。相邻元素颜色相同的数目为 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>queries[i].length&nbsp;== 2</code></li>\n",
    "\t<li><code>0 &lt;= index<sub>i</sub>&nbsp;&lt;= n - 1</code></li>\n",
    "\t<li><code>1 &lt;=&nbsp; color<sub>i</sub>&nbsp;&lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-adjacent-elements-with-the-same-color](https://leetcode.cn/problems/number-of-adjacent-elements-with-the-same-color/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-adjacent-elements-with-the-same-color](https://leetcode.cn/problems/number-of-adjacent-elements-with-the-same-color/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[0,2],[1,2],[3,1],[1,1],[2,1]]', '1\\n[[0,100000]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, q: List[List[int]]) -> List[int]:\n",
    "        a = [0] * n\n",
    "        def same(i):\n",
    "            if i >= 0 and i + 1 < n and a[i] == a[i + 1] and a[i] > 0:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        ans = 0\n",
    "        b = []\n",
    "        for i, c in q:\n",
    "            ans -= same(i)\n",
    "            ans -= same(i - 1)\n",
    "            a[i] = c\n",
    "            ans += same(i)\n",
    "            ans += same(i - 1)\n",
    "            b.append(ans)\n",
    "        return b\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        dp, cnt = [0] * (n + 2), 0\n",
    "        for i in range(len(queries)):\n",
    "            idx, color = queries[i]\n",
    "            if dp[idx+1] == color:  \n",
    "                queries[i] = cnt\n",
    "                continue\n",
    "            if dp[idx+1] != 0:\n",
    "                if dp[idx+1] == dp[idx]:    cnt -= 1\n",
    "                if dp[idx+1] == dp[idx+2]:  cnt -= 1\n",
    "            dp[idx+1] = color\n",
    "            if dp[idx+1] == dp[idx]:    cnt += 1\n",
    "            if dp[idx+1] == dp[idx+2]:  cnt += 1\n",
    "            queries[i] = cnt\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        nums = [0]*n\n",
    "        an = []\n",
    "        s = 0\n",
    "        for index, color in queries:\n",
    "            if color == nums[index]:\n",
    "                an.append(s)\n",
    "                continue\n",
    "            if index < n-1 and nums[index+1] != 0 and nums[index+1] == color:\n",
    "                s += 1\n",
    "            elif index < n-1 and nums[index+1] != 0 and nums[index+1] == nums[index]:\n",
    "                s -= 1\n",
    "            if index > 0 and nums[index-1] != 0 and nums[index-1] == color:\n",
    "                s += 1\n",
    "            elif index > 0 and nums[index-1] != 0 and nums[index-1] == nums[index]:\n",
    "                s -= 1\n",
    "            nums[index] = color\n",
    "            an.append(s)\n",
    "\n",
    "        return an"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        nums = Counter()\n",
    "        ans = [0]*(len(queries)+1)\n",
    "        for i, (idx, color) in enumerate(queries):\n",
    "            a = ans[i-1] if i > 0 else 0\n",
    "            if nums[idx]:\n",
    "                if nums[idx-1]==nums[idx]: a -= 1\n",
    "                if nums[idx]==nums[idx+1]: a -= 1\n",
    "\n",
    "            nums[idx] = color\n",
    "            if nums[idx-1]==nums[idx]: a += 1\n",
    "            if nums[idx]==nums[idx+1]: a += 1\n",
    "            ans[i] = a\n",
    "        return ans[:-1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        l = [0] * n\n",
    "        cnt = 0\n",
    "        ret = []\n",
    "        for i, c in queries:\n",
    "            if l[i] == c:\n",
    "                ret.append(cnt)\n",
    "                continue\n",
    "            if l[i] != 0:\n",
    "                if i > 0:\n",
    "                    if l[i] == l[i - 1]:\n",
    "                        cnt -= 1\n",
    "                if i < n - 1:\n",
    "                    if l[i] == l[i + 1]:\n",
    "                        cnt -= 1\n",
    "            l[i] = c\n",
    "            if l[i] != 0:\n",
    "                if i > 0:\n",
    "                    if l[i] == l[i - 1]:\n",
    "                        cnt += 1\n",
    "                if i < n - 1:\n",
    "                    if l[i] == l[i + 1]:\n",
    "                        cnt += 1\n",
    "            ret.append(cnt)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        arr = [0] * n\n",
    "        ans = []\n",
    "        dp = [0] * n\n",
    "        tmp = 0\n",
    "        for q in queries:\n",
    "            index, color = q\n",
    "            before, after = arr[index], color\n",
    "            if before == after:\n",
    "                ans.append(tmp)\n",
    "                continue\n",
    "            arr[index] = color\n",
    "            # print(arr)\n",
    "            if index >= 1 and arr[index-1] != 0:\n",
    "                if after == arr[index-1]:\n",
    "                    tmp += 1\n",
    "                if before == arr[index-1]:\n",
    "                    tmp -= 1\n",
    "            if index <= n-2 and arr[index+1] != 0:\n",
    "                if after == arr[index+1]:\n",
    "                    tmp += 1\n",
    "                if before == arr[index+1]:\n",
    "                    tmp -= 1\n",
    "            ans.append(tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans=[]\n",
    "        res=0\n",
    "        #修改一个只会影响左右两边\n",
    "        nums=[0]*n\n",
    "        for x,y in queries:\n",
    "            if x>0 and nums[x]==nums[x-1] and nums[x]!=0:\n",
    "                res-=1\n",
    "            if x+1<n and nums[x]==nums[x+1] and nums[x]!=0:\n",
    "                res-=1\n",
    "            nums[x]=y\n",
    "            if x>0 and nums[x]==nums[x-1] and nums[x]!=0:\n",
    "                res+=1\n",
    "            if x+1<n and nums[x]==nums[x+1] and nums[x]!=0:\n",
    "                res+=1\n",
    "            ans.append(res)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        l = [0] * n\n",
    "        result = 0\n",
    "        ans = []\n",
    "        for i in queries:\n",
    "            a = l[i[0]]\n",
    "            l[i[0]] = i[1]\n",
    "            if a == i[1]:\n",
    "                ans.append(result)\n",
    "                continue\n",
    "            elif a != 0:\n",
    "                if i[0] < n - 1:\n",
    "                    if a == l[i[0] + 1]:\n",
    "                        result -= 1\n",
    "                if i[0] > 0:\n",
    "                    if a == l[i[0] - 1]:\n",
    "                        result -= 1\n",
    "            if i[0] < n - 1:\n",
    "                if l[i[0]] == l[i[0] + 1]:\n",
    "                    result += 1\n",
    "            if i[0] > 0:\n",
    "                if l[i[0]] == l[i[0] - 1]:\n",
    "                    result += 1\n",
    "            ans.append(result)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, q: List[List[int]]) -> List[int]:\n",
    "        lq=len(q)\n",
    "        res=[0]*lq\n",
    "        a=[0]*n\n",
    "        cur=0\n",
    "        index=0\n",
    "        for i,c in q:\n",
    "            if a[i]!=0:\n",
    "                if i!=0 and a[i-1]==a[i]:\n",
    "                    cur-=1\n",
    "                if i+1!=n and a[i+1]==a[i]:\n",
    "                    cur-=1\n",
    "            a[i]=c\n",
    "            if i!=0 and a[i-1]==c:\n",
    "                cur+=1\n",
    "            if i+1!=n and a[i+1]==c:\n",
    "                cur+=1\n",
    "            res[index]=cur\n",
    "            index+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        color = [0] * n\n",
    "        ret = [0] * len(queries)\n",
    "        for i in range(len(queries)):\n",
    "            idx, c = queries[i]\n",
    "            old = color[idx]\n",
    "            v = ret[i - 1]\n",
    "            if old == c:\n",
    "                ret[i] = v\n",
    "                continue\n",
    "            if idx > 0 and color[idx - 1]:\n",
    "                if color[idx - 1] == old:\n",
    "                    v -= 1\n",
    "                elif color[idx - 1] == c:\n",
    "                    v += 1\n",
    "            if idx < n - 1 and color[idx + 1]:\n",
    "                if color[idx + 1] == old:\n",
    "                    v -= 1\n",
    "                elif color[idx + 1] == c:\n",
    "                    v += 1\n",
    "            ret[i] = v\n",
    "            color[idx] = c\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        color_arr = [0] * (n + 2)\n",
    "        tmp = 0\n",
    "        ans = [0] * (len(queries))\n",
    "        for i in range(len(queries)):\n",
    "            same_before = color_arr[queries[i][0] + 1] == color_arr[queries[i][0]] and color_arr[queries[i][0] + 1] != 0\n",
    "            same_after = color_arr[queries[i][0] + 1] == color_arr[queries[i][0] + 2] and color_arr[queries[i][0] + 1] != 0\n",
    "            color_arr[queries[i][0] + 1] = queries[i][1]\n",
    "            if color_arr[queries[i][0] + 1] == color_arr[queries[i][0] + 2] and color_arr[queries[i][0] + 1] != 0:\n",
    "                if not same_after:\n",
    "                    tmp += 1\n",
    "            else:\n",
    "                if same_after:\n",
    "                    tmp = tmp - 1 if tmp - 1 >= 0 else 0\n",
    "            if color_arr[queries[i][0] + 1] == color_arr[queries[i][0]] and color_arr[queries[i][0] + 1] != 0:\n",
    "                if not same_before:\n",
    "                    tmp += 1\n",
    "            else:\n",
    "                if same_before:\n",
    "                    tmp = tmp - 1 if tmp - 1 >= 0 else 0\n",
    "            ans[i] = tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        color = [0] * n\n",
    "        cnt = 0\n",
    "        ans = []\n",
    "        for i, c in queries:\n",
    "            if color[i]:\n",
    "                if i and color[i - 1] == color[i]: cnt -= 1\n",
    "                if i < n - 1 and color[i + 1] == color[i]: cnt -= 1\n",
    "            color[i] = c\n",
    "            if i and color[i - 1] == color[i]: cnt += 1\n",
    "            if i < n - 1 and color[i + 1] == color[i]: cnt += 1\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        nums = [0] * n\n",
    "        l = len(queries)\n",
    "        ans = []\n",
    "        cnt = 0\n",
    "        for i, x in queries:\n",
    "            if i > 0 and nums[i] == nums[i - 1] and nums[i] != 0:\n",
    "                cnt -= 1\n",
    "            if i + 1 < n and nums[i] == nums[i + 1] and nums[i] != 0:\n",
    "                cnt -= 1\n",
    "            nums[i] = x\n",
    "            if i > 0 and nums[i] == nums[i - 1] and  nums[i] != 0:\n",
    "                cnt += 1\n",
    "            if i + 1 < n and nums[i] == nums[i + 1] and nums[i] != 0:\n",
    "                cnt += 1\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        nums = [0]*n\n",
    "        cnt = 0\n",
    "        ans = []\n",
    "        for index,color in queries:\n",
    "            # 填过颜色\n",
    "            if nums[index]:\n",
    "                if index > 0 and nums[index] == nums[index-1]:\n",
    "                    cnt -= 1\n",
    "                if index < n-1 and nums[index] == nums[index+1]:\n",
    "                    cnt -= 1\n",
    "            # 改变颜色\n",
    "            nums[index] = color\n",
    "            if index > 0 and nums[index] == nums[index-1]:\n",
    "                cnt += 1\n",
    "            if index < n-1 and nums[index] == nums[index+1]:\n",
    "                cnt += 1\n",
    "            ans.append(cnt)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans=[]\n",
    "        nums=[0]*n\n",
    "        record=0\n",
    "        for i,x in queries:\n",
    "            pre=nums[i]\n",
    "            nums[i]=x\n",
    "            if i!=n-1 and nums[i]==nums[i+1]:\n",
    "                record += 1\n",
    "            if i!=n-1 and pre!=0 and pre==nums[i+1]:\n",
    "                record -= 1\n",
    "            if i!=0 and nums[i]==nums[i-1]:\n",
    "                record += 1\n",
    "            if i!=0 and pre!=0 and pre==nums[i-1]:\n",
    "                record -= 1\n",
    "            ans.append(record)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        nums = [0 for _ in range(n)]\n",
    "        count = 0\n",
    "        ans=[]\n",
    "        for query in queries:\n",
    "            posi = query[0]\n",
    "            if nums[posi] == 0:\n",
    "                nums[posi] = query[1]\n",
    "                if posi!=0 and nums[posi-1]==nums[posi]:\n",
    "                    count+=1\n",
    "                if posi!=n-1 and nums[posi+1]==nums[posi]:\n",
    "                    count+=1\n",
    "                ans.append(count)\n",
    "            else:\n",
    "                if nums[posi] == query[1]:\n",
    "                    ans.append(count)\n",
    "                    continue\n",
    "                if posi!=0 and nums[posi-1]==nums[posi]:\n",
    "                    count-=1\n",
    "                if posi!=n-1 and nums[posi+1]==nums[posi]:\n",
    "                    count-=1\n",
    "                nums[posi] = query[1]\n",
    "                if posi!=0 and nums[posi-1]==nums[posi]:\n",
    "                    count+=1\n",
    "                if posi!=n-1 and nums[posi+1]==nums[posi]:\n",
    "                    count+=1\n",
    "                ans.append(count)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        arr = [0] * n\n",
    "        now = 0\n",
    "        res = []\n",
    "        \n",
    "        for i, c in queries:\n",
    "            if arr[i] != 0:\n",
    "                if i > 0 and arr[i] == arr[i - 1]:\n",
    "                    now -= 1\n",
    "                if i + 1 < n and arr[i] == arr[i + 1]:\n",
    "                    now -= 1\n",
    "            \n",
    "            arr[i] = c\n",
    "            if i > 0 and arr[i] == arr[i - 1]:\n",
    "                now += 1\n",
    "            if i + 1 < n and arr[i] == arr[i + 1]:\n",
    "                now += 1\n",
    "                \n",
    "            res.append(now)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        cnt = 0\n",
    "        nums = [0]*n\n",
    "        ans = []\n",
    "        for index, color in queries:\n",
    "            if nums[index]:\n",
    "                if index > 0 and nums[index-1] == nums[index]:\n",
    "                    cnt -= 1\n",
    "                if index < n-1 and nums[index] == nums[index+1]:\n",
    "                    cnt -= 1\n",
    "            nums[index] = color\n",
    "            if index > 0 and nums[index-1] == nums[index]:\n",
    "                cnt += 1\n",
    "            if index < n-1 and nums[index] == nums[index+1]:\n",
    "                cnt += 1\n",
    "            ans.append(cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        if n == 1:\n",
    "            return [0] * len(queries)\n",
    "        arr = [0] * n\n",
    "        count = 0\n",
    "        res = []\n",
    "        for index, value in queries:\n",
    "            if arr[index] == value:\n",
    "                res.append(count)\n",
    "                continue\n",
    "\n",
    "            if index == 0:\n",
    "                if arr[index + 1] == value:\n",
    "                    count += 1\n",
    "                elif arr[index + 1] == arr[index] != 0:\n",
    "                    count -= 1\n",
    "            elif index == n-1:\n",
    "                if arr[index - 1] == value:\n",
    "                    count += 1\n",
    "                elif arr[index - 1] == arr[index] != 0:\n",
    "                    count -= 1\n",
    "            else:\n",
    "                if arr[index + 1] == value:\n",
    "                    count += 1\n",
    "                elif arr[index + 1] == arr[index] != 0:\n",
    "                    count -= 1\n",
    "                \n",
    "                if arr[index - 1] == value:\n",
    "                    count += 1\n",
    "                elif arr[index - 1] == arr[index] != 0:\n",
    "                    count -= 1\n",
    "            arr[index] = value\n",
    "            res.append(count)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ele_colors = [0] * n\n",
    "        ans = [0]\n",
    "        for index, color in queries:\n",
    "            cnt = ans[-1]\n",
    "            prev_color = ele_colors[index]\n",
    "            if color == prev_color:\n",
    "                ans.append(cnt)\n",
    "                continue\n",
    "                \n",
    "            if index - 1 >= 0 and prev_color != 0 and ele_colors[index - 1] == prev_color:\n",
    "                cnt -= 1\n",
    "            elif index - 1 >= 0 and ele_colors[index - 1] == color:\n",
    "                cnt += 1\n",
    "                \n",
    "            if index + 1 < n and prev_color != 0 and ele_colors[index + 1] == prev_color:\n",
    "                cnt -= 1\n",
    "            elif index + 1 < n and ele_colors[index + 1] == color:\n",
    "                cnt += 1  \n",
    "            ele_colors[index] = color\n",
    "            ans.append(cnt)\n",
    "        ans.pop(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        pre = 0\n",
    "        ans = []\n",
    "        paints = defaultdict(int)\n",
    "        for k in queries:\n",
    "            index, color = k[0], k[1]\n",
    "            if color == paints[index]:\n",
    "                ans.append(pre)\n",
    "            else:\n",
    "                if index == 0:\n",
    "                    if paints[index] == paints[index + 1] and paints[index] != 0:\n",
    "                        pre -= 1\n",
    "                    paints[index] = color\n",
    "                    if paints[index] == paints[index + 1] and paints[index] != 0:\n",
    "                        pre += 1\n",
    "                elif index == n - 1:\n",
    "                    if paints[index] == paints[index - 1] and paints[index] != 0:\n",
    "                        pre -= 1\n",
    "                    paints[index] = color\n",
    "                    if paints[index] == paints[index - 1] and paints[index] != 0:\n",
    "                        pre += 1\n",
    "                else:\n",
    "                    if paints[index] == paints[index - 1] and paints[index] != 0:\n",
    "                        pre -= 1\n",
    "                    if paints[index] == paints[index + 1] and paints[index] != 0:\n",
    "                        pre -= 1\n",
    "                    paints[index] = color\n",
    "                    if paints[index] == paints[index - 1] and paints[index] != 0:\n",
    "                        pre += 1\n",
    "                    if paints[index] == paints[index + 1] and paints[index] != 0:\n",
    "                        pre += 1     \n",
    "                ans.append(pre)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ori_list = [0] * (n + 2)\n",
    "        answer = []\n",
    "\n",
    "        for i in queries:\n",
    "            idx = i[0] + 1\n",
    "            col = i[1]\n",
    "\n",
    "            ans = answer[-1] if answer else 0\n",
    "            # if ori_list[idx] == 0:\n",
    "            #     if ori_list[idx - 1] == col:\n",
    "            #         ans += 1\n",
    "            #     if ori_list[idx + 1] == col:\n",
    "            #         ans += 1\n",
    "            #     ori_list[idx] = col\n",
    "            if ori_list[idx] != col:\n",
    "                if ori_list[idx] != 0:\n",
    "                    if ori_list[idx - 1] == ori_list[idx]:\n",
    "                        ans -= 1\n",
    "                    if ori_list[idx + 1] == ori_list[idx]:\n",
    "                        ans -= 1\n",
    "                if ori_list[idx - 1] == col:\n",
    "                    ans += 1\n",
    "                if ori_list[idx + 1] == col:\n",
    "                    ans += 1\n",
    "                ori_list[idx] = col\n",
    "            \n",
    "            answer.append(ans)\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        answer = [0 for _ in range(len(queries))]\n",
    "        num = [0 for _ in range(n)]\n",
    "        num[queries[0][0]] = queries[0][1]\n",
    "        num_same = [0 for _ in range(n)]\n",
    "        if n == 1:\n",
    "            return answer\n",
    "        for i in range(1, len(queries)):\n",
    "            index = queries[i][0]\n",
    "            color = queries[i][1]\n",
    "            num[index] = color\n",
    "            answer[i] = answer[i-1]\n",
    "            if index == 0:\n",
    "                if num[1] == num[0] and num_same[index] == 0:\n",
    "                    answer[i] = answer[i - 1] + 1\n",
    "                    num_same[index] = 1\n",
    "                elif num[1] != num[0] and num_same[index] == 1:\n",
    "                    answer[i] = answer[i - 1] - 1\n",
    "                    num_same[index] = 0\n",
    "            elif index == (n-1):\n",
    "                if num[-2] == num[-1] and (num_same[index - 1] == 0):\n",
    "                    answer[i] = answer[i - 1] + 1\n",
    "                    num_same[index - 1] = 1\n",
    "                elif num[-2] != num[-1] and num_same[index - 1] == 1:\n",
    "                    answer[i] = answer[i - 1] - 1\n",
    "                    num_same[index - 1] = 0\n",
    "            else:\n",
    "                if num[index - 1] == num[index] and num_same[index - 1] == 0:\n",
    "                    answer[i] = answer[i - 1] + 1\n",
    "                    num_same[index - 1] = 1\n",
    "                elif num[index - 1] != num[index] and num_same[index - 1] == 1:\n",
    "                    answer[i] = answer[i - 1] - 1\n",
    "                    num_same[index - 1] = 0\n",
    "                if num[index + 1] == num[index] and num_same[index] == 0:\n",
    "                    answer[i] = answer[i] + 1\n",
    "                    num_same[index] = 1\n",
    "                elif num[index + 1] != num[index] and num_same[index] == 1:\n",
    "                    answer[i] = answer[i] - 1\n",
    "                    num_same[index] = 0\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        nums = Counter()\n",
    "        ans = [0]*(len(queries)+1)\n",
    "        for i, (idx, color) in enumerate(queries):\n",
    "            a = ans[i-1] if i > 0 else 0\n",
    "            if nums[idx]:\n",
    "                a -= (nums[idx-1]==nums[idx]) + (nums[idx]==nums[idx+1])\n",
    "            nums[idx] = color\n",
    "            a += (nums[idx-1]==nums[idx]) + (nums[idx]==nums[idx+1])\n",
    "            ans[i] = a\n",
    "        return ans[:-1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ori_list = [0] * (n + 2)\n",
    "        answer = []\n",
    "        tmp = [[] for i in range(n)]\n",
    "\n",
    "        for i in queries:\n",
    "            idx = i[0] + 1\n",
    "            col = i[1]\n",
    "\n",
    "            ans = answer[-1] if answer else 0\n",
    "            if ori_list[idx] == 0:\n",
    "                if ori_list[idx - 1] == col:\n",
    "                    ans += 1\n",
    "                if ori_list[idx + 1] == col:\n",
    "                    ans += 1\n",
    "                ori_list[idx] = col\n",
    "            elif ori_list[idx] != col:\n",
    "                if ori_list[idx - 1] == ori_list[idx]:\n",
    "                    ans -= 1\n",
    "                if ori_list[idx + 1] == ori_list[idx]:\n",
    "                    ans -= 1\n",
    "                if ori_list[idx - 1] == col:\n",
    "                    ans += 1\n",
    "                if ori_list[idx + 1] == col:\n",
    "                    ans += 1\n",
    "                ori_list[idx] = col\n",
    "            \n",
    "            answer.append(ans)\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ori_list = [0] * (n + 2)\n",
    "        answer = []\n",
    "        tmp = [[] for i in range(n)]\n",
    "\n",
    "        for i in queries:\n",
    "            idx = i[0] + 1\n",
    "            col = i[1]\n",
    "\n",
    "            ans = answer[-1] if answer else 0\n",
    "            # if ori_list[idx] == 0:\n",
    "            #     if ori_list[idx - 1] == col:\n",
    "            #         ans += 1\n",
    "            #     if ori_list[idx + 1] == col:\n",
    "            #         ans += 1\n",
    "            #     ori_list[idx] = col\n",
    "            if ori_list[idx] != col:\n",
    "                if ori_list[idx] != 0:\n",
    "                    if ori_list[idx - 1] == ori_list[idx]:\n",
    "                        ans -= 1\n",
    "                    if ori_list[idx + 1] == ori_list[idx]:\n",
    "                        ans -= 1\n",
    "                if ori_list[idx - 1] == col:\n",
    "                    ans += 1\n",
    "                if ori_list[idx + 1] == col:\n",
    "                    ans += 1\n",
    "                ori_list[idx] = col\n",
    "            \n",
    "            answer.append(ans)\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ori_list = [0] * (n + 2)\n",
    "        answer = []\n",
    "        tmp = [[] for i in range(n)]\n",
    "\n",
    "        for i in queries:\n",
    "            idx = i[0] + 1\n",
    "            col = i[1]\n",
    "\n",
    "            ans = answer[-1] if answer else 0\n",
    "            # if ori_list[idx] == 0:\n",
    "            #     if ori_list[idx - 1] == col:\n",
    "            #         ans += 1\n",
    "            #     if ori_list[idx + 1] == col:\n",
    "            #         ans += 1\n",
    "            #     ori_list[idx] = col\n",
    "            if ori_list[idx] != col:\n",
    "                if ori_list[idx] != 0:\n",
    "                    if ori_list[idx - 1] == ori_list[idx]:\n",
    "                        ans -= 1\n",
    "                    if ori_list[idx + 1] == ori_list[idx]:\n",
    "                        ans -= 1\n",
    "                if ori_list[idx - 1] == col:\n",
    "                    ans += 1\n",
    "                if ori_list[idx + 1] == col:\n",
    "                    ans += 1\n",
    "                ori_list[idx] = col\n",
    "            \n",
    "            answer.append(ans)\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ori_list = [0] * (n + 2)\n",
    "        answer = []\n",
    "        tmp = [[] for i in range(n)]\n",
    "\n",
    "        for i in queries:\n",
    "            idx = i[0] + 1\n",
    "            col = i[1]\n",
    "\n",
    "            ans = answer[-1] if answer else 0\n",
    "            if ori_list[idx] == 0:\n",
    "                if ori_list[idx - 1] == col:\n",
    "                    ans += 1\n",
    "                if ori_list[idx + 1] == col:\n",
    "                    ans += 1\n",
    "                ori_list[idx] = col\n",
    "            elif ori_list[idx] != col and ori_list[idx] != 0:\n",
    "                if ori_list[idx - 1] == ori_list[idx]:\n",
    "                    ans -= 1\n",
    "                if ori_list[idx + 1] == ori_list[idx]:\n",
    "                    ans -= 1\n",
    "                if ori_list[idx - 1] == col:\n",
    "                    ans += 1\n",
    "                if ori_list[idx + 1] == col:\n",
    "                    ans += 1\n",
    "                ori_list[idx] = col\n",
    "            \n",
    "            answer.append(ans)\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ori_list = [0] * (n + 2)\n",
    "        answer = []\n",
    "        tmp = [[] for i in range(n)]\n",
    "\n",
    "        for i in queries:\n",
    "            idx = i[0] + 1\n",
    "            col = i[1]\n",
    "\n",
    "            ans = answer[-1] if answer else 0\n",
    "            if ori_list[idx] == 0:\n",
    "                if ori_list[idx - 1] == col:\n",
    "                    ans += 1\n",
    "                if ori_list[idx + 1] == col:\n",
    "                    ans += 1\n",
    "                ori_list[idx] = col\n",
    "            elif ori_list[idx] != col and ori_list != 0:\n",
    "                if ori_list[idx - 1] == ori_list[idx]:\n",
    "                    ans -= 1\n",
    "                if ori_list[idx + 1] == ori_list[idx]:\n",
    "                    ans -= 1\n",
    "                if ori_list[idx - 1] == col:\n",
    "                    ans += 1\n",
    "                if ori_list[idx + 1] == col:\n",
    "                    ans += 1\n",
    "                ori_list[idx] = col\n",
    "            \n",
    "            answer.append(ans)\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ori_list = [0] * (n + 2)\n",
    "        answer = []\n",
    "        tmp = [[] for i in range(n)]\n",
    "\n",
    "        for i in queries:\n",
    "            idx = i[0] + 1\n",
    "            col = i[1]\n",
    "\n",
    "            ans = answer[-1] if answer else 0\n",
    "            # if ori_list[idx] == 0:\n",
    "            #     if ori_list[idx - 1] == col:\n",
    "            #         ans += 1\n",
    "            #     if ori_list[idx + 1] == col:\n",
    "            #         ans += 1\n",
    "            #     ori_list[idx] = col\n",
    "            if ori_list[idx] != col:\n",
    "                if ori_list[idx] != 0:\n",
    "                    if ori_list[idx - 1] == ori_list[idx]:\n",
    "                        ans -= 1\n",
    "                    if ori_list[idx + 1] == ori_list[idx]:\n",
    "                        ans -= 1\n",
    "                if ori_list[idx - 1] == col:\n",
    "                    ans += 1\n",
    "                if ori_list[idx + 1] == col:\n",
    "                    ans += 1\n",
    "                ori_list[idx] = col\n",
    "            \n",
    "            answer.append(ans)\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        # 思路1 分类讨论 维护一个nums数组\n",
    "        def judge(a, b, c):\n",
    "            if a == b == c != 0:\n",
    "                return 2\n",
    "            elif a == b != 0 or 0 != b == c:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        nums = [0] * (n + 2)\n",
    "        ans = []\n",
    "        cnt = 0\n",
    "        for i, c in queries:\n",
    "            i += 1\n",
    "            cnt += (judge(nums[i - 1], c, nums[i + 1]) - judge(nums[i - 1], nums[i], nums[i + 1]))\n",
    "            ans.append(cnt)\n",
    "            nums[i] = c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        a, cnt = [0] * (n + 2), 0  # 避免讨论下标出界的情况\n",
    "        for i, c in queries:\n",
    "            i += 1  # 下标改成从 1 开始\n",
    "            if a[i]: cnt -= (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            a[i] = c\n",
    "            cnt += (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            ans.append(cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        colors = [0]*n\n",
    "        result = []\n",
    "        pre = 0\n",
    "        for i, c in queries:\n",
    "            sub = 0\n",
    "            if(i-1 >= 0 and colors[i]!=0 and colors[i-1] == colors[i]):\n",
    "                sub += 1\n",
    "            if(i+1 <= n-1 and colors[i]!=0 and colors[i+1] == colors[i]):\n",
    "                sub += 1\n",
    "            \n",
    "            colors[i] = c\n",
    "            add = 0\n",
    "            if(i-1 >= 0 and colors[i]!=0 and colors[i-1] == colors[i]):\n",
    "                add += 1\n",
    "            if(i+1 <= n-1 and colors[i]!=0 and colors[i+1] == colors[i]):\n",
    "                add += 1\n",
    "            pre = pre - sub + add \n",
    "            result.append(pre)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        arr = [0] * (n + 2)\n",
    "        ans = [0]\n",
    "        for i, j in queries:\n",
    "            nei = 0\n",
    "            if arr[i + 1] == arr[i] and arr[i] != 0:\n",
    "                nei += 1\n",
    "            if arr[i + 1] == arr[i + 2] and arr[i + 2] != 0:\n",
    "                nei += 1\n",
    "            add = 0\n",
    "            if j == arr[i]:\n",
    "                add += 1\n",
    "            if j == arr[i + 2]:\n",
    "                add += 1\n",
    "            arr[i + 1] = j\n",
    "            ans.append(ans[-1] - nei + add)\n",
    "        return ans[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        def refresh_answer(answer,nums,pair,i,length):\n",
    "            if pair[0]!=0 and pair[0]!=length-1:\n",
    "                if nums[pair[0]]!=0 and nums[pair[0]-1]==nums[pair[0]] and nums[pair[0]-1]!=pair[1]:\n",
    "                    answer[i] += -1\n",
    "                if nums[pair[0]-1]!=0 and nums[pair[0]-1]!=nums[pair[0]] and nums[pair[0]-1]==pair[1]:\n",
    "                    answer[i] += 1\n",
    "                if nums[pair[0]+1]!=0 and nums[pair[0]+1]!=nums[pair[0]] and nums[pair[0]+1]==pair[1]:\n",
    "                    answer[i] += 1\n",
    "                if nums[pair[0]]!=0 and nums[pair[0]+1]==nums[pair[0]] and nums[pair[0]+1]!=pair[1]:\n",
    "                    answer[i] += -1\n",
    "            elif pair[0]==0 and nums[0]!=0 and nums[0]==nums[1] and nums[0]!=pair[1]:\n",
    "                answer[i] += -1\n",
    "            elif pair[0]==0 and nums[1]!=0 and nums[0]!=nums[1] and nums[1]==pair[1]:\n",
    "                answer[i] += 1\n",
    "            elif pair[0]==length-1 and nums[-1]!=0 and nums[-1]==nums[-2] and nums[-1]!=pair[1]:\n",
    "                answer[i] += -1\n",
    "            elif pair[0]==length-1 and nums[-2]!=0 and nums[-1]!=nums[-2] and nums[-2]==pair[1]:\n",
    "                answer[i] += 1\n",
    "            \n",
    "        length = len(queries)\n",
    "        nums = [0]*n\n",
    "        answer = [0]*length\n",
    "        if n==1:\n",
    "            return answer\n",
    "        for i in range(length):\n",
    "            refresh_answer(answer,nums,queries[i],i,n)\n",
    "            nums[queries[i][0]] = queries[i][1]\n",
    "        for i in range(1,length):\n",
    "            answer[i] += answer[i-1]\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = list()\n",
    "        nums = [0] * n\n",
    "        cnt = 0\n",
    "        for x, y in queries:\n",
    "            if nums[x] != 0:\n",
    "                if x > 0:\n",
    "                    cnt -= (nums[x] == nums[x - 1])\n",
    "                if x < n - 1:\n",
    "                    cnt -= (nums[x] == nums[x + 1])\n",
    "            nums[x] = y\n",
    "            if x > 0:\n",
    "                cnt += (nums[x] == nums[x - 1])\n",
    "            if x < n - 1:\n",
    "                cnt += (nums[x] == nums[x + 1])\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        m=len(queries)\n",
    "        res=[0]*m\n",
    "        cnt=[0]*(n+2)\n",
    "        tot=0\n",
    "        for i,[id,c] in enumerate(queries):\n",
    "            if cnt[id+1]==0:\n",
    "                tot +=1 if cnt[id]==c else 0\n",
    "                tot +=1 if cnt[id+2]==c else 0\n",
    "            else:\n",
    "                '''\n",
    "                tot +=0 cnt[id]==0 or cnt[id-1]!=c else 1\n",
    "                tot +=0 if id==n-1 or cnt[id+1]==0 or cnt[id+1]!=c else 1\n",
    "                tot -=0 if id==0 or cnt[id-1]==0 or cnt[id-1]!=cnt[id] else 1\n",
    "                tot +=0 if id==n-1 or cnt[id+1]==0 or cnt[id+1]!=cnt[id] else 1\n",
    "                '''\n",
    "                if cnt[id+1]!=c:\n",
    "                    if cnt[id+1]==cnt[id]:\n",
    "                        tot -=1\n",
    "                    else:\n",
    "                        tot +=1 if cnt[id]==c else 0\n",
    "                    if cnt[id+1]==cnt[id+2]:\n",
    "                        tot -=1\n",
    "                    else:\n",
    "                        tot +=1 if cnt[id+2]==c else 0\n",
    "\n",
    "            cnt[id+1]=c\n",
    "            res[i]=tot\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        helper = [0] * n\n",
    "        ans = [0]\n",
    "        for q in queries:\n",
    "            index = q[0]\n",
    "            color = q[1]\n",
    "            pre = helper[max(index - 1, 0):min(index + 2, n)]\n",
    "            a1 = 0 \n",
    "            for i in range(len(pre) - 1):\n",
    "                if pre[i] == pre[i + 1] and pre[i] != 0:\n",
    "                    a1 += 1\n",
    "            helper[index] = color\n",
    "            pre = helper[max(index - 1, 0):min(index + 2, n)]\n",
    "            a2 = 0 \n",
    "            for i in range(len(pre) - 1):\n",
    "                if pre[i] == pre[i + 1] and pre[i] != 0:\n",
    "                    a2 += 1\n",
    "            mid = ans[-1]\n",
    "            ans.append(mid + a2 - a1)\n",
    "        return ans[1:]\n",
    "            \n",
    "                    \n",
    "                    \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        a, cnt = [0] * (n + 2), 0  # 避免讨论下标出界的情况\n",
    "        for i, c in queries:\n",
    "            i += 1  # 下标改成从 1 开始\n",
    "            if a[i]: cnt -= (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            a[i] = c\n",
    "            cnt += (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            ans.append(cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        a, cnt = [0] * (n + 2), 0  # 避免讨论下标出界的情况\n",
    "        for i, c in queries:\n",
    "            i += 1  # 下标改成从 1 开始\n",
    "            if a[i]: cnt -= (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            a[i] = c\n",
    "            cnt += (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            ans.append(cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        a, cnt = [0] * (n + 2), 0  # 避免讨论下标出界的情况\n",
    "        for i, c in queries:\n",
    "            i += 1  # 下标改成从 1 开始\n",
    "            if a[i] > 0: \n",
    "                cnt -= (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            a[i] = c\n",
    "            cnt += (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            ans.append(cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        a = [0] * (n+2)\n",
    "        cnt = 0\n",
    "        for i,c in queries:\n",
    "            i += 1\n",
    "            if a[i]:\n",
    "                cnt -= (a[i] == a[i-1]) + (a[i] == a[i+1])\n",
    "            a[i] = c\n",
    "            cnt += (a[i] == a[i-1]) + (a[i] == a[i+1])\n",
    "            ans.append(cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        a, cnt = [0] * (n + 2), 0  # 避免讨论下标出界的情况\n",
    "        for i, c in queries:\n",
    "            i += 1  # 下标改成从 1 开始\n",
    "            if a[i]: cnt -= (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            a[i] = c\n",
    "            cnt += (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        tmp = [0]*n\n",
    "\n",
    "        ret = []\n",
    "        ans = 0\n",
    "        for i,c in queries:\n",
    "            if tmp[i]:\n",
    "                if i > 0 :\n",
    "                    ans -= int(tmp[i]==tmp[i-1])\n",
    "                if i<n-1:\n",
    "                    ans -= int(tmp[i]== tmp[i+1])\n",
    "            tmp[i] =c\n",
    "\n",
    "            if i > 0 :\n",
    "                ans += int(tmp[i]==tmp[i-1])\n",
    "            if i<n-1:\n",
    "                ans += int(tmp[i]== tmp[i+1])\n",
    "            ret.append(ans)\n",
    "        return ret\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        a, cnt = [0] * (n + 2), 0  # 避免讨论下标出界的情况\n",
    "        for i, c in queries:\n",
    "            i += 1  # 下标改成从 1 开始\n",
    "            if a[i]: cnt -= (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            a[i] = c\n",
    "            cnt += (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        color, res, pres = [0 for _ in range(n)], [], 0\n",
    "        for x in queries:\n",
    "            if color[x[0]] != x[1]:\n",
    "                if color[x[0]] != 0:\n",
    "                    pres -= (x[0] and color[x[0]] == color[x[0] - 1]) + (x[0] < n - 1 and color[x[0]] == color[x[0] + 1])\n",
    "                pres += (x[0] and x[1] == color[x[0] - 1]) + (x[0] < n - 1 and x[1] == color[x[0] + 1])\n",
    "                color[x[0]] = x[1]\n",
    "            res.append(pres)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        nums = [0]*(n+2)\n",
    "        ans = []\n",
    "        for i, (idx, color) in enumerate(queries):\n",
    "            a = ans[-1] if ans else 0\n",
    "            if nums[idx]:\n",
    "                a -= (nums[idx-1]==nums[idx]) + (nums[idx]==nums[idx+1])\n",
    "            nums[idx] = color\n",
    "            a += (nums[idx-1]==nums[idx]) + (nums[idx]==nums[idx+1])\n",
    "            ans.append(a)\n",
    "\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        a, cnt = [0] * (n + 2), 0  # 避免讨论下标出界的情况\n",
    "        for i, c in queries:\n",
    "            i += 1  # 下标改成从 1 开始\n",
    "            if a[i]: cnt -= (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            a[i] = c\n",
    "            cnt += (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            ans.append(cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = 0\n",
    "        ret = []\n",
    "        nums = [0] * n\n",
    "        for i in range(len(queries)):\n",
    "            tmp = 0\n",
    "            idx = queries[i][0]\n",
    "            if 0 <= idx - 1 < n:\n",
    "                if nums[idx - 1] == nums[idx] and nums[idx - 1] != 0:\n",
    "                    tmp -= 1\n",
    "            if 0 <= idx + 1 < n:\n",
    "                if nums[idx + 1] == nums[idx] and nums[idx + 1] != 0:\n",
    "                    tmp -= 1\n",
    "            nums[idx] = queries[i][1]\n",
    "            if 0 <= idx - 1 < n:\n",
    "                if nums[idx - 1] == nums[idx]:\n",
    "                    tmp += 1\n",
    "            if 0 <= idx + 1 < n:\n",
    "                if nums[idx + 1] == nums[idx]:\n",
    "                    tmp += 1\n",
    "            ans += tmp\n",
    "            ret.append(ans)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        res = [0]*len(queries)\n",
    "        color = [0]*n\n",
    "        color[queries[0][0]] = queries[0][1]\n",
    "        for i in range(1,len(queries)):\n",
    "            yuan = 0 \n",
    "            xian = 0\n",
    "            q = queries[i]\n",
    "            if 0 <= q[0] + 1 < n:\n",
    "                if color[q[0]+1] == color[q[0]] and color[q[0]+1] != 0:\n",
    "                    yuan += 1\n",
    "                if color[q[0]+1] == q[1]:\n",
    "                    xian += 1\n",
    "            if 0 <= q[0] - 1 < n:\n",
    "                if color[q[0]-1] == color[q[0]] and color[q[0]-1] != 0:\n",
    "                    yuan += 1\n",
    "                if color[q[0]-1] == q[1]:\n",
    "                    xian += 1\n",
    "            color[q[0]] = q[1]\n",
    "            res[i] = res[i-1] + xian - yuan\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        l=len(queries)\n",
    "        res=[0]*(l)\n",
    "        tmp=[0]*(n+1)\n",
    "        tmp1=[False for _ in range(n+1)]\n",
    "        now=0\n",
    "        for i,(idx,c) in enumerate(queries):\n",
    "            res[i]=now\n",
    "            if tmp[idx]!=c:\n",
    "                tmp[idx]=c\n",
    "                res[i]-=sum(tmp1[idx:idx+2])\n",
    "                tmp1[idx]=tmp[idx]==tmp[idx-1]\n",
    "                tmp1[idx+1]=tmp[idx]==tmp[idx+1]\n",
    "                res[i]+=sum(tmp1[idx:idx+2])\n",
    "                now=res[i]\n",
    "            # print(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        def refresh_answer(answer,nums,pair,i,length):\n",
    "            if pair[0]==0 and nums[0]!=0 and nums[0]==nums[1] and nums[0]!=pair[1]:\n",
    "                answer[i] += -1\n",
    "            elif pair[0]==0 and nums[1]!=0 and nums[0]!=nums[1] and nums[1]==pair[1]:\n",
    "                answer[i] += 1\n",
    "            elif pair[0]==length-1 and nums[-1]!=0 and nums[-1]==nums[-2] and nums[-1]!=pair[1]:\n",
    "                answer[i] += -1\n",
    "            elif pair[0]==length-1 and nums[-2]!=0 and nums[-1]!=nums[-2] and nums[-2]==pair[1]:\n",
    "                answer[i] += 1\n",
    "            elif pair[0]!=0 and pair[0]!=length-1:\n",
    "                if nums[pair[0]]!=0 and nums[pair[0]-1]==nums[pair[0]] and nums[pair[0]-1]!=pair[1]:\n",
    "                    answer[i] += -1\n",
    "                if nums[pair[0]-1]!=0 and nums[pair[0]-1]!=nums[pair[0]] and nums[pair[0]-1]==pair[1]:\n",
    "                    answer[i] += 1\n",
    "                if nums[pair[0]+1]!=0 and nums[pair[0]+1]!=nums[pair[0]] and nums[pair[0]+1]==pair[1]:\n",
    "                    answer[i] += 1\n",
    "                if nums[pair[0]]!=0 and nums[pair[0]+1]==nums[pair[0]] and nums[pair[0]+1]!=pair[1]:\n",
    "                    answer[i] += -1\n",
    "        length = len(queries)\n",
    "        nums = [0]*n\n",
    "        answer = [0]*length\n",
    "        if n==1:\n",
    "            return answer\n",
    "        for i in range(length):\n",
    "            refresh_answer(answer,nums,queries[i],i,n)\n",
    "            nums[queries[i][0]] = queries[i][1]\n",
    "        for i in range(1,length):\n",
    "            answer[i] += answer[i-1]\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        g = [0] * n\n",
    "        cnt = 0\n",
    "        for i, c in queries:\n",
    "            if g[i] != 0:\n",
    "                if i > 0: cnt -= g[i] == g[i-1]\n",
    "                if i < n-1: cnt -= g[i] == g[i+1]\n",
    "            g[i] = c\n",
    "            if i > 0: cnt += g[i] == g[i-1]\n",
    "            if i < n-1: cnt += g[i] == g[i+1]\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        def refresh_answer(answer,nums,pair,i):\n",
    "            length = len(nums)\n",
    "            if pair[0]==0 and nums[0]!=0 and nums[0]==nums[1] and nums[0]!=pair[1]:\n",
    "                answer[i] += -1\n",
    "            elif pair[0]==0 and nums[1]!=0 and nums[0]!=nums[1] and nums[1]==pair[1]:\n",
    "                answer[i] += 1\n",
    "            elif pair[0]==length-1 and nums[-1]!=0 and nums[-1]==nums[-2] and nums[-1]!=pair[1]:\n",
    "                answer[i] += -1\n",
    "            elif pair[0]==length-1 and nums[-2]!=0 and nums[-1]!=nums[-2] and nums[-2]==pair[1]:\n",
    "                answer[i] += 1\n",
    "            elif pair[0]!=0 and pair[0]!=length-1:\n",
    "                if nums[pair[0]]!=0 and nums[pair[0]-1]==nums[pair[0]] and nums[pair[0]-1]!=pair[1]:\n",
    "                    answer[i] += -1\n",
    "                if nums[pair[0]-1]!=0 and nums[pair[0]-1]!=nums[pair[0]] and nums[pair[0]-1]==pair[1]:\n",
    "                    answer[i] += 1\n",
    "                if nums[pair[0]+1]!=0 and nums[pair[0]+1]!=nums[pair[0]] and nums[pair[0]+1]==pair[1]:\n",
    "                    answer[i] += 1\n",
    "                if nums[pair[0]]!=0 and nums[pair[0]+1]==nums[pair[0]] and nums[pair[0]+1]!=pair[1]:\n",
    "                    answer[i] += -1\n",
    "        length = len(queries)\n",
    "        nums = [0]*n\n",
    "        answer = [0]*length\n",
    "        if n==1:\n",
    "            return answer\n",
    "        for i in range(length):\n",
    "            refresh_answer(answer,nums,queries[i],i)\n",
    "            nums[queries[i][0]] = queries[i][1]\n",
    "        for i in range(1,length):\n",
    "            answer[i] += answer[i-1]\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        colors = [0]*n\n",
    "        result = []\n",
    "        pre = 0\n",
    "        for i, c in queries:\n",
    "            sub = 0\n",
    "            if(i-1 >= 0 and colors[i]!=0 and colors[i-1] == colors[i]):\n",
    "                sub += 1\n",
    "            if(i+1 <= n-1 and colors[i]!=0 and colors[i+1] == colors[i]):\n",
    "                sub += 1\n",
    "            \n",
    "            colors[i] = c\n",
    "            add = 0\n",
    "            if(i-1 >= 0 and colors[i]!=0 and colors[i-1] == colors[i]):\n",
    "                add += 1\n",
    "            if(i+1 <= n-1 and colors[i]!=0 and colors[i+1] == colors[i]):\n",
    "                add += 1\n",
    "            pre = pre - sub + add \n",
    "            result.append(pre)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = [0]\n",
    "        col = {}\n",
    "        for query in queries:\n",
    "            pos = query[0]\n",
    "            c = query[1]\n",
    "            f = 0\n",
    "            if pos not in col:\n",
    "                col[pos] = c\n",
    "            elif col[pos] !=c:\n",
    "                if pos - 1 in col and col[pos-1]==col[pos]:\n",
    "                    f-=1\n",
    "                if pos + 1 in col and col[pos+1]==col[pos]:\n",
    "                    f-=1\n",
    "                col[pos]=c\n",
    "            else:\n",
    "                ans.append(ans[-1])\n",
    "                continue\n",
    "            if pos - 1 in col and col[pos-1]==c:\n",
    "                f+=1\n",
    "            if pos + 1 in col and col[pos+1]==c:\n",
    "                f+=1\n",
    "            ans.append(ans[-1]+f)\n",
    "        return ans[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = 0\n",
    "        ret = []\n",
    "        nums = [0] * n\n",
    "        for i in range(len(queries)):\n",
    "            tmp = 0\n",
    "            idx = queries[i][0]\n",
    "            if 0 <= idx - 1 < n:\n",
    "                if nums[idx - 1] == nums[idx] and nums[idx - 1] != 0:\n",
    "                    tmp -= 1\n",
    "            if 0 <= idx + 1 < n:\n",
    "                if nums[idx + 1] == nums[idx] and nums[idx + 1] != 0:\n",
    "                    tmp -= 1\n",
    "            nums[idx] = queries[i][1]\n",
    "            if 0 <= idx - 1 < n:\n",
    "                if nums[idx - 1] == nums[idx]:\n",
    "                    tmp += 1\n",
    "            if 0 <= idx + 1 < n:\n",
    "                if nums[idx + 1] == nums[idx]:\n",
    "                    tmp += 1\n",
    "            ans += tmp\n",
    "            ret.append(ans)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        a, cnt = [0] * (n + 2), 0  # 避免讨论下标出界的情况\n",
    "        for i, c in queries:\n",
    "            i += 1  # 下标改成从 1 开始\n",
    "            if a[i]: cnt -= (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            a[i] = c\n",
    "            cnt += (a[i] == a[i - 1]) + (a[i] == a[i + 1])\n",
    "            ans.append(cnt)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
